
/*
 *
 * santas-tour.h
 *
 */

typedef struct _node
{
    double x, y;
    int    number;
    // (# of nodes within distance radius)/(radius**2*M_PI)
    double density; 
    double density_radius;
    // which "bucket" does this node go into?
    double grey_value;
    struct _node *prev, *next;

} node;

typedef struct _basic_node
{
    double x, y;
    int    number;
    struct _basic_node /* *prev, */ *next;

} basic_node;

// #define QBOX_OVERLAP_MAX  0.4
// #define QBOX_OVERLAP_MIN  0.02

typedef struct _qt_box
{    
    double  xmin, ymin, xmax, ymax;

} qt_box;

typedef struct _qt_node
{
    qt_box box;
    union
    {
        basic_node *pleafnode;
        basic_node *pconflicts;
    };
    struct _qt_node *child[4];

} qt_node;

typedef struct _quadtree
{
    qt_node   *root;
    unsigned  depth;    // Max depth of tree:  0-based.
//    float     overlap;  // Overlapped ratio of qt_box.

} quadtree;

typedef enum
{
    NW = 0,
    NE = 1,
    SW = 2,
    SE = 3

} quadenum;

typedef struct _extra
{
    int    number;
    double grey_x, grey_y;
    struct _qt_node *qtnode;

} extra;

typedef struct _grey_node
{
//    int x, y;
    int    nodecnt;
    double grey_value;

} grey_node;

extern void find_paths( basic_node *sorted_on_x, basic_node *sorted_on_y, node **path1, node **path2);

extern quadtree *qt_create( qt_box box, int nodecnt, int depth /*, float overlap */ );
extern void      qt_destroy( quadtree *qt );
extern qt_node  *qt_insert( quadtree *qt, basic_node *node, qt_box *box );
extern void      qt_search( quadtree *qt, qt_box *sbox, basic_node *outlst[], int *outinidx, int inmaxidx );

extern void      qt_box_init( qt_box *qb, double xmin, double ymin, double xmax, double ymax );

/* EOF */
